/*************************************************************************
 * File Name:    Subsets_II.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sat 02 Nov 2013 07:12:52 PM CST
 * 
 * Description:  
 |-----------------------------------------------------------------------
 | Problem: Subsets II
 | Given a collection of integers that might contain duplicates, S,
 | return all possible subsets.
 |
 | Note:
 | Elements in a subset must be in non-descending order.
 | The solution set must not contain duplicate subsets.
 |
 | For example,
 | If S = [1,2,2], a solution is:
 |
 | [
 |   [2],
 |   [1],
 |   [1,2,2],
 |   [2,2],
 |   [1,2],
 |   []
 | ]
 |-----------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S)
    {
        map<int, int> m;
        for (size_t i = 0; i < S.size(); ++i) {
            ++m[S[i]];
        }
        vector<int> num;
        int t, lim = 1;
        for (map<int,int>::iterator it = m.begin(); it != m.end(); ++it) {
            num.push_back(it->first);
            lim *= it->second + 1;
        }
        
        vector<int> tsub;
        vector<vector<int> > ans;
        for (int i = 0; i < lim; ++i) {
            t = i;
            tsub.clear();
            for (int j = 0; j < num.size(); ++j) {
                for (int k = t % (m[num[j]] + 1); k > 0; --k) {
                    tsub.push_back(num[j]);
                }
                t /= m[num[j]] + 1;
            }
            sort(tsub.begin(), tsub.end());
            ans.push_back(tsub);
        }
        return ans;
    }

    vector<vector<int> > subsetsWithDup2(vector<int> &S)
    {
        set<vector<int> > ans;
        int N = S.size();
        int lim = 1 << N;
        
        vector<int> t;
        for (int i = 0; i < lim; ++i) {
            t.clear();
            for (int j = 0; j < N; ++j) {
                if (i & (1 << j)) t.push_back(S[j]);
            }
            sort(t.begin(), t.end());
            ans.insert(t);
        }
        return vector<vector<int> >(ans.begin(), ans.end());
    }
};

int 
main(int argc, char *argv[])
{
    Solution sol;
    vector<int> S;

    S.push_back(1);
    S.push_back(1);

    vector<vector<int> > ans = sol.subsetsWithDup(S);
    for (size_t i = 0; i < ans.size(); ++i) {
        for (size_t j = 0; j < ans[i].size(); ++j) {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}
